#include <stdio.h>
#include "clib_container_single_linked_list.h"
#include "../../memory/clib_memory.h"


struct clib_container_single_linked_list {
    //首个元素指针
    struct clib_container_single_linked_list_entry *first;
    //最后一个元素指针
    struct clib_container_single_linked_list_entry *last;
    //当前元素个数
    size_t current_item_size;
};

struct clib_container_single_linked_list_entry {
    //下一个元素指针
    struct clib_container_single_linked_list_entry *next;
    //当前元素数据指针
    void *data;
};

struct clib_container_single_linked_list_entry *
clib_container_single_linked_list_entry_get_next(struct clib_container_single_linked_list_entry *entry) {
    clib_check_if_true_return_value(entry == NULL, NULL);
    return entry->next;
}

void *
clib_container_single_linked_list_entry_get_data(struct clib_container_single_linked_list_entry *entry) {
    clib_check_if_true_return_value(entry == NULL, NULL);
    return entry->data;
}


struct clib_container_single_linked_list *clib_container_single_linked_list_create() {
    //申请内存空间
    struct clib_container_single_linked_list *linked_list = clib_memory_allocator_malloc_default(
            sizeof(struct clib_container_single_linked_list));
    if (linked_list == NULL) {
        return NULL;
    }
    linked_list->current_item_size = 0;
    linked_list->first = NULL;
    linked_list->last = NULL;
    return linked_list;
}


int
clib_container_single_linked_list_destroy(struct clib_container_single_linked_list *list) {
    clib_check_if_true_return_value(list == NULL, CLIB_RES_PARAM_ERROR);
    clib_check_if_true_return_value(list->current_item_size != 0, CLIB_RES_PARAM_ERROR);
    clib_memory_allocator_free_default(list);
    return CLIB_RES_OK;
}


size_t clib_container_single_linked_list_get_current_size(struct clib_container_single_linked_list *list) {
    clib_check_if_true_return_value(list == NULL, 0);
    return list->current_item_size;
}


struct clib_container_single_linked_list_entry *
clib_container_single_linked_list_get_first(struct clib_container_single_linked_list *list) {
    clib_check_if_true_return_value(list == NULL, NULL);
    clib_check_if_true_return_value(list->first == NULL, NULL);
    return list->first;
}

struct clib_container_single_linked_list_entry *
clib_container_single_linked_list_get_last(struct clib_container_single_linked_list *list) {
    clib_check_if_true_return_value(list == NULL, NULL);
    clib_check_if_true_return_value(list->last == NULL, NULL);
    return list->last;
}

static struct clib_container_single_linked_list_entry *clib_container_single_linked_list_new_entry(void *data) {
    //创建一个节点
    struct clib_container_single_linked_list_entry *new_entry = clib_memory_allocator_malloc_default(
            sizeof(struct clib_container_single_linked_list_entry));
    clib_check_if_true_return_value(new_entry == NULL, NULL);
    new_entry->data = data;
    new_entry->next = NULL;
    return new_entry;
}

int clib_container_single_linked_list_insert_next(struct clib_container_single_linked_list *list,
                                                  struct clib_container_single_linked_list_entry *entry,
                                                  void *data) {
    clib_check_if_true_return_value(list == NULL, CLIB_RES_PARAM_ERROR);
    clib_check_if_true_return_value(entry == NULL, CLIB_RES_PARAM_ERROR);

    struct clib_container_single_linked_list_entry *new_entry = clib_container_single_linked_list_new_entry(data);
    clib_check_if_true_return_value(new_entry == NULL, CLIB_RES_MEMORY_ERROR);

    //当entry的下一个节点为NULL时，说明时最后一个节点，则更新最后节点指针
    if (entry->next == NULL) {
        list->last = new_entry;
    }
    //插入
    new_entry->next = entry->next;
    entry->next = new_entry;
    //增加元素个数
    list->current_item_size += 1;

    return CLIB_RES_OK;
}


int
clib_container_single_linked_list_insert_pre(
        struct clib_container_single_linked_list *list,
        struct clib_container_single_linked_list_entry *entry,
        void *data) {
    clib_check_if_true_return_value(list == NULL, CLIB_RES_PARAM_ERROR);
    clib_check_if_true_return_value(entry == NULL, CLIB_RES_PARAM_ERROR);

    struct clib_container_single_linked_list_entry *new_entry = clib_container_single_linked_list_new_entry(data);
    clib_check_if_true_return_value(new_entry == NULL, CLIB_RES_MEMORY_ERROR);

    if (entry == list->first) {
        //该元素是首元素，则将新数据添加在首元素位置
        return clib_container_single_linked_list_insert_first(list, data);
    }
    //找到该元素的上一个元素
    struct clib_container_single_linked_list_entry *last_pre_entry = list->first;
    while (last_pre_entry->next != entry) {
        last_pre_entry = last_pre_entry->next;
    }
    new_entry->next = last_pre_entry->next;
    last_pre_entry->next = new_entry;
    list->current_item_size += 1;
    return CLIB_RES_OK;
}


int clib_container_single_linked_list_insert_first(struct clib_container_single_linked_list *list,
                                                   void *data) {
    clib_check_if_true_return_value(list == NULL, CLIB_RES_PARAM_ERROR);
    struct clib_container_single_linked_list_entry *new_entry = clib_container_single_linked_list_new_entry(data);
    clib_check_if_true_return_value(new_entry == NULL, CLIB_RES_MEMORY_ERROR);
    if (list->first == NULL) {
        list->first = new_entry;
        list->last = new_entry;
        new_entry->next = NULL;
    } else {
        new_entry->next = list->first;
        list->first = new_entry;
    }
    //增加元素个数
    list->current_item_size += 1;
    return CLIB_RES_OK;
}


int clib_container_single_linked_list_insert_last(struct clib_container_single_linked_list *list,
                                                  void *data) {
    clib_check_if_true_return_value(list == NULL, CLIB_RES_PARAM_ERROR);
    struct clib_container_single_linked_list_entry *new_entry = clib_container_single_linked_list_new_entry(data);
    clib_check_if_true_return_value(new_entry == NULL, CLIB_RES_MEMORY_ERROR);
    if (list->last == NULL) {
        list->first = new_entry;
        list->last = new_entry;
    } else {
        new_entry->next = NULL;
        list->last->next = new_entry;
        list->last = new_entry;
    }
    //增加元素个数
    list->current_item_size += 1;
    return CLIB_RES_OK;
}


void *clib_container_single_linked_list_delete_first(struct clib_container_single_linked_list *list) {
    clib_check_if_true_return_value(list == NULL, NULL);
    if (list->first == NULL) {
        return NULL;
    }
    void *result_data = list->first->data;
    if (list->first->next == NULL) {
        //只有一个元素，删除之后元素个数为空，则last也应该为空
        list->last = NULL;
    }
    void *free_item_next = list->first->next;
    clib_memory_allocator_free_default(list->first);
    list->first = free_item_next;
    //减少元素个数
    list->current_item_size -= 1;
    return result_data;
}


void *clib_container_single_linked_list_delete_last(struct clib_container_single_linked_list *list) {
    clib_check_if_true_return_value(list == NULL, NULL);
    if (list->last == NULL) {
        return NULL;
    }
    void *result_data = list->last->data;
    if (list->first->next == NULL) {
        //只有一个元素，删除之后元素个数为空，则first也应该为空
        list->first = NULL;
        clib_memory_allocator_free_default(list->last);
        list->last = NULL;
    } else {
        struct clib_container_single_linked_list_entry *last_pre_entry = list->first;
        while (last_pre_entry->next != list->last) {
            last_pre_entry = last_pre_entry->next;
        }
        last_pre_entry->next = NULL;
        clib_memory_allocator_free_default(list->last);
        list->last = last_pre_entry;
    }
    //减少元素个数
    list->current_item_size -= 1;
    return result_data;
}


void *clib_container_single_linked_list_delete(struct clib_container_single_linked_list *list,
                                               struct clib_container_single_linked_list_entry *entry) {
    clib_check_if_true_return_value(list == NULL, NULL);
    if (entry == list->first) {
        //删除首节点
        return clib_container_single_linked_list_delete_first(list);
    } else if (entry == list->last) {
        //删除尾节点
        return clib_container_single_linked_list_delete_last(list);
    } else {
        struct clib_container_single_linked_list_entry *delete_pre_entry = list->first;
        while (delete_pre_entry->next != entry) {
            delete_pre_entry = delete_pre_entry->next;
        }
        void *return_data = delete_pre_entry->next->data;
        struct clib_container_single_linked_list_entry *delete_entry = delete_pre_entry->next;
        delete_pre_entry->next = delete_pre_entry->next->next;
        clib_memory_allocator_free_default(delete_entry);
        list->current_item_size -= 1;
        return return_data;
    }
}


void *
clib_container_single_linked_list_replace(struct clib_container_single_linked_list *list,
                                          struct clib_container_single_linked_list_entry *entry,
                                          void *new_data) {
    clib_check_if_true_return_value(list == NULL, NULL);
    clib_check_if_true_return_value(entry == NULL, NULL);
    void *return_data = entry->data;
    entry->data = new_data;
    return return_data;
}


void *
clib_container_single_linked_list_replace_first(struct clib_container_single_linked_list *list,
                                                void *new_data) {
    return clib_container_single_linked_list_replace(list, list->first, new_data);
}

void *
clib_container_single_linked_list_replace_last(struct clib_container_single_linked_list *list,
                                               void *new_data) {
    return clib_container_single_linked_list_replace(list, list->last, new_data);
}

struct clib_container_single_linked_list_entry *
clib_container_single_linked_list_get_entry_by_index(struct clib_container_single_linked_list *list, int index) {
    clib_check_if_true_return_value(index < 0, NULL);
    clib_check_if_true_return_value(index >= list->current_item_size, NULL);
    int find_index = 0;
    struct clib_container_single_linked_list_entry *find_entry = list->first;
    while (find_entry != NULL) {
        if (find_index == index) {
            break;
        }
        find_index += 1;
        find_entry = find_entry->next;
    }
    return find_entry;
}


void *
clib_container_single_linked_list_delete_entry_by_index(struct clib_container_single_linked_list *list, int index) {
    clib_check_if_true_return_value(index < 0, NULL);
    clib_check_if_true_return_value(index >= list->current_item_size, NULL);
    size_t current_item_size = list->current_item_size;
    if (index == 0) {
        //删除头节点
        return clib_container_single_linked_list_delete_first(list);
    } else if (index + 1 == current_item_size) {
        //删除尾节点
        return clib_container_single_linked_list_delete_last(list);
    } else {
        //其他节点
        //找到删除的节点的前一个节点
        struct clib_container_single_linked_list_entry *delete_pre_entry = clib_container_single_linked_list_get_entry_by_index(
                list,
                index - 1);
        clib_check_if_true_return_value(delete_pre_entry == NULL, NULL);
        void *return_data = delete_pre_entry->next->data;
        struct clib_container_single_linked_list_entry *delete_entry = delete_pre_entry->next;
        delete_pre_entry->next = delete_pre_entry->next->next;
        clib_memory_allocator_free_default(delete_entry);
        list->current_item_size -= 1;
        return return_data;
    }
}


int
clib_container_single_linked_list_moveto_next(
        struct clib_container_single_linked_list *list,
        struct clib_container_single_linked_list_entry *entry1,
        struct clib_container_single_linked_list_entry *entry2) {
    clib_check_if_true_return_value(entry1 == entry2, CLIB_RES_PARAM_ERROR);

    if (entry1 == list->first) {
        //移动的是首节点
        list->first = entry1->next;
        entry1->next = entry2->next;
        entry2->next = entry1;
        return CLIB_RES_OK;
    } else if (entry1 == list->last) {
        //移动的是尾节点
        struct clib_container_single_linked_list_entry *move_pre_entry = list->first;
        while (move_pre_entry->next != entry1) {
            move_pre_entry = move_pre_entry->next;
        }
        list->last = move_pre_entry;
        move_pre_entry->next = NULL;
        entry1->next = entry2->next;
        entry2->next = entry1;
        return CLIB_RES_OK;
    }
    if (entry2 == list->last){
        list->last = entry1;
    }
    struct clib_container_single_linked_list_entry *move_pre_entry = list->first;
    while (move_pre_entry->next != entry1) {
        move_pre_entry = move_pre_entry->next;
    }
    move_pre_entry->next = entry1->next;

    entry1->next = entry2->next;
    entry2->next = entry1;
    return CLIB_RES_OK;
}


int
clib_container_single_linked_list_moveto_pre(
        struct clib_container_single_linked_list *list,
        struct clib_container_single_linked_list_entry *entry1,
        struct clib_container_single_linked_list_entry *entry2) {
    clib_check_if_true_return_value(entry1 == entry2, CLIB_RES_PARAM_ERROR);
    if (entry2 == list->first){
        struct clib_container_single_linked_list_entry *move_pre_entry = list->first;
        while (move_pre_entry->next != entry1) {
            move_pre_entry = move_pre_entry->next;
        }
        if (entry1 == list->last){
            list->last = move_pre_entry;
        }
        move_pre_entry->next = entry1->next;

        list->first = entry1;
        entry1->next = entry2;
        return CLIB_RES_OK;
    }
    struct clib_container_single_linked_list_entry *move_pre_entry = list->first;
    while (move_pre_entry->next != entry2) {
        move_pre_entry = move_pre_entry->next;
    }
    return clib_container_single_linked_list_moveto_next(list,entry1,move_pre_entry);
}


